/*  slflpwmd.cpp  by K.Tsuru  */
// function ID = 2005   DRADIX
/***********************************
SLong class
It provides the value of M^d mod n.
************************************/
#ifndef SN_H
#include "sn.h"
#endif
SLong MpowMod(const SLong& M, ulong d, const SLong& n){
    SLong x(1), m(M);

    if(d == 0) return x;    // = 1

    while(d){
        if( (d % 2) == 0){
            d /= 2;
            m = (m*m) % n;
        } else {
            d--;
            x = (x*m) % n;
        }
    }
    return x;
}